/*
 * Copyright (C) 2012 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.collect;

import com.google.caliper.BeforeExperiment;
import com.google.caliper.Benchmark;
import com.google.caliper.Param;
import com.google.common.base.Optional;
import com.google.common.primitives.Ints;

import java.util.List;
import java.util.Random;

/**
 * Benchmarks for the {@code TreeTraverser} operations on binary trees.
 *
 * @author Louis Wasserman
 */
public class BinaryTreeTraverserBenchmark
{
    private static class BinaryNode
    {
        final int x;
        final Optional<BinaryNode> left;
        final Optional<BinaryNode> right;

        BinaryNode(int x, Optional<BinaryNode> left, Optional<BinaryNode> right)
        {
            this.x = x;
            this.left = left;
            this.right = right;
        }
    }

    enum Topology
    {
        BALANCED
                {
                    @Override
                    Optional<BinaryNode> createTree(int size, Random rng)
                    {
                        if (size == 0)
                        {
                            return Optional.absent();
                        }
                        else
                        {
                            int leftChildSize = (size - 1) / 2;
                            int rightChildSize = size - 1 - leftChildSize;
                            return Optional.of(
                                    new BinaryNode(
                                            rng.nextInt(), createTree(leftChildSize, rng), createTree(rightChildSize, rng)));
                        }
                    }
                },
        ALL_LEFT
                {
                    @Override
                    Optional<BinaryNode> createTree(int size, Random rng)
                    {
                        Optional<BinaryNode> root = Optional.absent();
                        for (int i = 0; i < size; i++)
                        {
                            root = Optional.of(new BinaryNode(rng.nextInt(), root, Optional.<BinaryNode>absent()));
                        }
                        return root;
                    }
                },
        ALL_RIGHT
                {
                    @Override
                    Optional<BinaryNode> createTree(int size, Random rng)
                    {
                        Optional<BinaryNode> root = Optional.absent();
                        for (int i = 0; i < size; i++)
                        {
                            root = Optional.of(new BinaryNode(rng.nextInt(), Optional.<BinaryNode>absent(), root));
                        }
                        return root;
                    }
                },
        RANDOM
                {
                    /**
                     * Generates a tree with topology selected uniformly at random from the topologies of binary
                     * trees of the specified size.
                     */
                    @Override
                    Optional<BinaryNode> createTree(int size, Random rng)
                    {
                        int[] keys = new int[size];
                        for (int i = 0; i < size; i++)
                        {
                            keys[i] = rng.nextInt();
                        }
                        return createTreap(Ints.asList(keys));
                    }

                    // See http://en.wikipedia.org/wiki/Treap for details on the algorithm.
                    private Optional<BinaryNode> createTreap(List<Integer> keys)
                    {
                        if (keys.isEmpty())
                        {
                            return Optional.absent();
                        }
                        int minIndex = 0;
                        for (int i = 1; i < keys.size(); i++)
                        {
                            if (keys.get(i) < keys.get(minIndex))
                            {
                                minIndex = i;
                            }
                        }
                        Optional<BinaryNode> leftChild = createTreap(keys.subList(0, minIndex));
                        Optional<BinaryNode> rightChild = createTreap(keys.subList(minIndex + 1, keys.size()));
                        return Optional.of(new BinaryNode(keys.get(minIndex), leftChild, rightChild));
                    }
                };

        abstract Optional<BinaryNode> createTree(int size, Random rng);
    }

    private static final TreeTraverser<BinaryNode> VIEWER =
            new TreeTraverser<BinaryNode>()
            {
                @Override
                public Iterable<BinaryNode> children(BinaryNode root)
                {
                    return Optional.presentInstances(ImmutableList.of(root.left, root.right));
                }
            };

    enum Traversal
    {
        PRE_ORDER
                {
                    @Override
                    <T> Iterable<T> view(T root, TreeTraverser<T> viewer)
                    {
                        return viewer.preOrderTraversal(root);
                    }
                },
        POST_ORDER
                {
                    @Override
                    <T> Iterable<T> view(T root, TreeTraverser<T> viewer)
                    {
                        return viewer.postOrderTraversal(root);
                    }
                },
        BREADTH_FIRST
                {
                    @Override
                    <T> Iterable<T> view(T root, TreeTraverser<T> viewer)
                    {
                        return viewer.breadthFirstTraversal(root);
                    }
                };

        abstract <T> Iterable<T> view(T root, TreeTraverser<T> viewer);
    }

    private Iterable<BinaryNode> view;

    @Param
    Topology topology;

    @Param({"1", "100", "10000", "1000000"})
    int size;

    @Param
    Traversal traversal;

    @Param({"1234"})
    SpecialRandom rng;

    @BeforeExperiment
    void setUp()
    {
        this.view = traversal.view(topology.createTree(size, rng).get(), VIEWER);
    }

    @Benchmark
    int traversal(int reps)
    {
        int tmp = 0;

        for (int i = 0; i < reps; i++)
        {
            for (BinaryNode node : view)
            {
                tmp += node.x;
            }
        }
        return tmp;
    }
}
